package leetcode.f1t100;

import java.util.Arrays;

/**
 * 给一个数组, 以及一个目标值, 得到数组3个元素相加最接近目标数的相加值
 * https://leetcode.com/problems/3sum-closest/
 * @Author lichongxiao
 * @Date 2022/9/28 15:49
 */
public class Q16_3SumClosest {
    public static void main(String[] args) {
        System.out.println(new Q16_3SumClosest().threeSumClosest(new int[]{-1,2,1,-4},1));
        System.out.println(new Q16_3SumClosest().threeSumClosest(new int[]{4,0,5,-5,3,3,0,-4,-5},-2));
    }
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans=Integer.MAX_VALUE;
        for (int i = 0; i < nums.length-2; i++) {
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int left = i+1,right = nums.length-1,sum;
            while(left < right){
                sum = nums[i]+nums[left]+nums[right];
                if(sum==target){
                    return sum;
                }
                if(Math.abs(sum-target) < Math.abs(ans-target)){
                    ans = sum;
                }
                if(sum>target){
                    right--;
                }else{
                    left++;
                }
            }
        }
        return ans;
    }
}
